package main

import (
	"fmt"
	"sort"
)

func main() {
	fmt.Printf("returnAllSubArray([]int{0}): %v\n", subsetsWithDup([]int{0}))
}

/**
要求，可以不按顺序，但是要去重， 比如 112  和 211 和 121 其实同一个
*/

/*
*
不按顺序了，那就先排序，相同的就划分为1组，然后就回到了 abc 的所有子串问题
// 要注意的是，a里面的数字可以取0次，1次，2次..., b,c 同理
*/
var ans [][]int

func subsetsWithDup(nums []int) [][]int {
	subArray := make([]int, len(nums))
	sort.Ints(nums)
	dfs1(nums, 0, subArray, 0)
	return ans
}

func dfs1(a []int, cur int, subArray []int, size int) {
	if cur == len(a) {
		newS := make([]int, len(subArray[:size]))
		copy(newS, subArray[:size])
		ans = append(ans, newS)
		return
	}
	next := cur + 1
	// 下一组的第一个数的位置
	for next < len(a) && a[next] == a[cur] {
		next++
	}
	// 当前组，要size个数，去执行f(i)
	dfs1(a, next, subArray, size)
	for ; cur < next; cur++ {
		// 当前组，要size+1个数，去执行f(i)
		subArray[size] = a[cur]
		size++
		dfs1(a, next, subArray, size)
	}
	return
}
